package com.li.link;

public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinelist circleSingleLinelist = new CircleSingleLinelist();
        circleSingleLinelist.addBoy(5);
        circleSingleLinelist.showboy();

        circleSingleLinelist.countBoy(1, 3, 5);
    }


}

//创建一个环形链表
class CircleSingleLinelist {
    //创建first节点
    private Boy first = new Boy(-1);

    //添加小孩节点，构建成环形链表
    public void addBoy(int numers) {
        if (numers < 1) {
            System.out.println("数据不正确");
            return;
        }
        Boy curboy = null;//辅助指针，帮助构建环形链表
        //使用for循环创建环形链表
        for (int i = 1; i <= numers; i++) {
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curboy = first;
            } else {
                curboy.setNext(boy);
                boy.setNext(first);
                curboy = boy;
            }

        }
    }

    public void showboy() {
        if (first == null) {
            System.out.println("空");
            return;
        }
        Boy curboy = first;
        while (true) {
            System.out.printf("小孩的编号为%d", curboy.getNo());
            if (curboy.getNext() == first) {
                break;
            }
            curboy = curboy.getNext();
        }

    }

    //根据输入，激素出出拳的顺序
    public void countBoy(int startNo, int countNum, int nums) {

        //先对数据进行校验
        if (first == null || startNo < 1 || startNo > nums) {

            System.out.println("参数输入有误，请重新输入");
            return;
        }
        //创建辅助指针，帮助完成小孩出圈
        Boy helper = first;
        //让helper指向环形链表最后的节点
        while (true) {
            if (helper.getNext() == first) {
                //说明指向最后一个节点
                break;
            }
            helper = helper.getNext();
        }
        //小孩报数前，先让first和helper移动startNo-1
        for (int j = 0; j < startNo - 1; j++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        while (true) {
            if (helper == first) {
             //说明只有一人
                break;
            }
            //让first和helper指针同时移动countNum - 1次
            for (int j = 0; j < countNum - 1; j++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //这时first指向小孩要出圈的节点
            System.out.printf("小孩%d出圈\n", first.getNo());
            first = first.getNext();
            helper.setNext(first);//把圈接上
        }

        System.out.printf("最后留在圈中的小孩编号为%d\n", first.getNo());
    }

}

//创建一个boy类表示一个节点
class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}